package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/partition-list/?envType=problem-list-v2&envId=linked-list
 * @create 2025/8/16 08:40
 * @since JDK17
 */

public class Solution20 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(), s = small;
        ListNode big = new ListNode(), b = big;
        for (ListNode p = head; p != null; p = p.next) {
            if (p.val < x) {
                s = s.next = p;
            } else {
                b = b.next = p;
            }
        }
        b.next = null;
        s.next = big.next;
        return small.next;
    }
}
